In wireless communication systems, multicasting allows a transmitter to send a packet only once, even if it needs to be delivered to a large number of receivers. When a source packet is sent out via multicasting, it is typical that not all the targeted receivers will recover the source packet. In existing protocols, when all receivers do not recover the source packet, the packet must be retransmitted. The practice of retransmitting the source packets creates inefficiency in wireless systems because some receivers recover data that they already possess.
Recently developed techniques, commonly known as Rateless Codes (RCs; also known as Fountain Codes) avoid this inefficiency by transmitting “derived packets” which are linear combinations of original packets. Rateless coding has been described and analyzed in a number of previous works, including: M. Luby, “LT codes,” in Proceedings of the ACM Symposium on Foundations of Computer Science, 2002; A. Shokrollahi, “Raptor codes,” in Proceedings of the International Symposium on Information Theory, 2004; U.S. Pat. No. 6,614,366 entitled “Information additive code generator and decoder for communication systems”; and U.S. Pat. No. 7,068,729 entitled “Multi-stage code generator and decoder for communication systems”. While such techniques are known in systems where no feedback from receivers to the sender is available, their application in systems with feedback, including Automatic Repeat Request (ARQ) and Hybrid-ARQ (HARQ) protocols is not well known.
To better understand the state of the art, a wireless communication system model 100 as shown in FIG. 1 is described. Assume a base station 110 wishes to send a number of source packets p1, . . . , pk to m user equipments (UEs) 120. The source packets are of the same size and the transmission is by means of multicast. The wireless channels between the base station 110 and the m UEs 120 are memoryless erasure channels that are independent of each other. Let ei, for i=1, . . . , m, denote the erasure rate of the channel between the base station 110 and UE i 120. In other words, the probability that UE i 120 receives a packet is 1−ei, and the probability that UE i 120 does not receive a packet is ei. A packet is considered as missing if a UE is unable to recover every bit in the packet using the physical layer forward error correction technologies. Each UE 120 is able to send a single bit acknowledgement/negative acknowledgement (ACK/NACK) feedback to the base station, informing it whether the packet is received or not. Without loss of generality, it is assumed that the base station 110 sends a packet at the first part of a timeslot, and the UEs 120 send the ACK/NACK at the second part of the timeslot.
The existing protocols without RCs are now described. Protocol 1 describes the existing protocol on the wireless communication system 100 with only two UEs (i.e., m=2 in FIG. 1), while Protocol 1a extends Protocol 1 to an arbitrary number of UEs.
Protocol 1
As shown in FIG. 1, a base station 110 retransmits the same packet until it receives at least one ACK from each UE 120 for this packet. It is noted that a UE may ACK a source packet more than once, when the source packet is retransmitted. Then, the base station 110 sends a new packet. Protocol 1 ensures that all UEs 120 receive all source packets.
To evaluate the performance of Protocol 1, the average (expected) overhead is computed. Overhead is the ratio of the total number of packet transmissions over the number of source packets. By definition, overhead is a number no less than 1, and a smaller overhead is desirable. According to Protocol 1, the number of transmissions of the same packet until both UEs receive it is equal to the larger of the transmissions of the same packet if they were independently sent to each UE. This can be mathematically expressed in the following description that can also be applied to multiple UEs.
Let Z be the number of transmissions of the same packet until both UEs receive it. Then, Z=max{X, Y}, where X and Y are independent geometric random variables with respective parameters 1−e1 and 1−e2. Specifically, for x, y=1, 2, . . . , Pr(X=x)=(1−e1)e1x−1 and Pr(Y=y)=(1−e2)e2y−1. The total number of packets sent in Protocol 1 such that all k source packets are received by both UEs is given by
                              ∑                      i            =            1                    k                ⁢                  Z          i                                    Equation        ⁢                                  ⁢                  (          1          )                    
where Zi are independent random variables with the same distribution as Z. Hence, the total number can be written as
                              ∑                      i            =            1                    k                ⁢                  max          ⁢                      {                                          X                i                            ,                              Y                i                                      }                                              Equation        ⁢                                  ⁢                  (          2          )                    
where X1, . . . , Xk are independent geometric random variables with parameter 1−e1, and Y1, . . . , Yk are independent geometric random variables with parameter 1−e2.
As shown by Equation (1), the average number of packets sent in Protocol 1 is given by kE(Z), and the expected overhead of Protocol 1 is given by E(Z). It can be shown that
                              E          ⁡                      (            Z            )                          =                              1                          1              -                              e                1                                              +                      1                          1              -                              e                2                                              -                      1                          1              -                                                e                  1                                ⁢                                  e                  2                                                                                        Equation        ⁢                                  ⁢                  (          3          )                    
Protocol 1 can be applied to the multicast model with an arbitrary number of UEs as follows.
Protocol 1a
In Protocol 1a, Protocol 1 is extended to multiple UEs. In Protocol 1a, the base station retransmits the same packet until it receives at least one ACK from every UE for this packet. Then, the base station sends a new packet. Protocol 1a ensures that every UE receives all source packets. Performance of this protocol is evaluated in a way similar to the approach taken for two UEs.
The present disclosure includes the use of rateless coding protocols and the efficiencies these deliver in systems where feedback information does exist. Having feedback information about which packets were and were not received can deliver significant additional advantages not realized in existing protocols. With the current availability of feedback data, new multicasting protocols are needed to allow for greater system efficiency.